package srcCycleCalculator;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

public class CycleCalculator
{
    private static int currentCycleCount = 0;
    private static double ComputeAdjustedListAverage(List<Double> values) 
    {
        double sum = 0;
        
        for (int i = 2; i < values.size() - 2; ++i)
        {
            sum += values.get(i);
        }
        
        return sum / (values.size() - 4);
    }
    private static HashMap<Integer, Integer> GenerateGraphMapping(int size, Random randomGenerator)
    {
        HashMap<Integer, Integer> graphMapping = new HashMap<Integer, Integer>();

        for (int i = 0; i < size; ++i)
        {
            int neighbor = randomGenerator.nextInt(size);
            graphMapping.put(i, neighbor);
        }

        return graphMapping;
    }
    private static int GetNextCycleNumber()
    {
        return ++currentCycleCount ;
    }
    /**
     * @param args
     * @throws Exception 
     */
    public static void main(String[] args) throws Exception
    {
        try
        {
            Random randomGenerator = new Random();
            
            BufferedWriter bufWriter = new BufferedWriter(
                    new FileWriter("CycleDetectorOutput.csv"));
            
            for (int size = 1; size < 30000; ++size)
            {
                List<Double> numCyclesList = new ArrayList<Double>();
                List<Double> avgCycleLengthList = new ArrayList<Double>();
                List<Double> avgCycleWeightList = new ArrayList<Double>();
                
                for (int i = 0; i < 10; ++i)
                {
                    HashMap<Integer, Integer> graphMapping = GenerateGraphMapping(size, randomGenerator);
                    
                    CycleCalculator cycleCalculator = new CycleCalculator(graphMapping);
            
                    cycleCalculator.ComputeCycleStatistics();
                    int numCycles = cycleCalculator.GetNumberOfCycles();
                    double avgCycleLength = cycleCalculator.GetAvgCycleLength();
                    double avgCycleWeight = cycleCalculator.GetAvgCycleWeight();
            
                    numCyclesList.add((double) numCycles);
                    avgCycleLengthList.add(avgCycleLength);
                    avgCycleWeightList.add(avgCycleWeight);
                }
                
                Collections.sort(numCyclesList);
                Collections.sort(avgCycleLengthList);
                Collections.sort(avgCycleWeightList);
                
                double avgNumCycles = ComputeAdjustedListAverage(numCyclesList);
                double avgCycleLength = ComputeAdjustedListAverage(avgCycleLengthList);
                double avgCycleWeight = ComputeAdjustedListAverage(avgCycleWeightList);
                
                /*
                System.out.println("size: " + size);
                System.out.println("avgNumCycles: " + avgNumCycles);
                System.out.println("avgCycleLength: " + avgCycleLength);
                System.out.println("avgCycleWeight: " + avgCycleWeight);
                */
                
                bufWriter.write(
                        String.format(
                                "%d, %f, %f, %f",
                                size,
                                avgNumCycles,
                                avgCycleLength,
                                avgCycleWeight));
                
                bufWriter.newLine();
                bufWriter.flush();
            }
        }
        catch (Exception ex)
        {
            ex.printStackTrace();
            throw ex;
        }
    }

    private HashMap<Integer, Integer> graphMapping;

    private HashMap<Integer, Integer> cycleLengthMap;

    private HashMap<Integer, Integer> cycleWeightMap;

    private HashMap<Integer, Integer> vertexToCycleNumberMap;

    private HashSet<Integer> unvisitedVertices;

    public CycleCalculator(HashMap<Integer, Integer> graphMapping)
    {
        this.graphMapping = graphMapping;

        this.cycleLengthMap = new HashMap<Integer, Integer>();
        this.cycleWeightMap = new HashMap<Integer, Integer>();
        this.vertexToCycleNumberMap = new HashMap<Integer, Integer>();

        InitializeUnvisitedNodes(graphMapping);
    }

    private void AddBranchVerticesEntriesToVertexToCycleMapping(
            int startVertex,
            int tortoiseSteps,
            int cycleNumber)
    {
        int currentVertex = startVertex;
        for (int i = 0; i < tortoiseSteps; ++i)
        {
            this.vertexToCycleNumberMap.put(currentVertex, cycleNumber);
            currentVertex = this.graphMapping.get(currentVertex);
        }
    }

    private void AddEntriesToVertexToCycleMapping(
            int startVertex,
            int cycleOffset,
            int cycleLength,
            int cycleNumber)
    {
        int currentVertex = startVertex;

        for (int i = 0; i < cycleOffset + cycleLength; ++i)
        {
            this.vertexToCycleNumberMap.put(currentVertex, cycleNumber);
            currentVertex = this.graphMapping.get(currentVertex);
        }
    }

    private int ComputeCycleLength(int startVertex, int cycleOffset)
    {
        int tortoiseVertex = startVertex;

        for (int i = 0; i < cycleOffset; ++i)
        {
            tortoiseVertex = this.graphMapping.get(tortoiseVertex);
        }

        int hareVertex = this.graphMapping.get(tortoiseVertex);
        int steps = 1;
        while (hareVertex != tortoiseVertex)
        {
            hareVertex = this.graphMapping.get(hareVertex);
            ++steps;
        }

        return steps;
    }

    private int ComputeCycleOffset(
            int startVertex,
            int hareVertex)
    {
        int tortoiseVertex = startVertex;
        int steps = 0;
        while (tortoiseVertex != hareVertex)
        {
            tortoiseVertex = this.graphMapping.get(tortoiseVertex);
            hareVertex = this.graphMapping.get(hareVertex);
            ++steps;
        }

        return steps;
    }

    private void ComputeCycleStatistics()
    {
        List<Integer> zeroInDegreeVertices = GetZeroInDegreeVertices();

        // visit the vertices with zero in-degree first
        while (!zeroInDegreeVertices.isEmpty())
        {
            int startVertex = zeroInDegreeVertices.get(0);
            RunTortoiseHareAlgorithm(startVertex);
            zeroInDegreeVertices.remove(0);
        }

        // if some vertices are still unvisited (the ones part of a pure cycle including self-loops), visit them
        while (!this.unvisitedVertices.isEmpty())
        {
            Iterator<Integer> it = unvisitedVertices.iterator();
            int startVertex = it.next();
            RunTortoiseHareAlgorithm(startVertex);
        }
    }

    private double GetAvgCycleLength()
    {
        int sum = 0;

        for (int weight : this.cycleLengthMap.values())
        {
            sum += weight;
        }

        return (double) sum / this.GetNumberOfCycles();
    }

    private double GetAvgCycleWeight()
    {
        int sum = 0;

        for (int weight : this.cycleWeightMap.values())
        {
            sum += weight;
        }

        return (double) sum / this.GetNumberOfCycles();
    }

    private int GetNumberOfCycles()
    {
        return this.cycleLengthMap.size();
    }

    private List<Integer> GetZeroInDegreeVertices()
    {
        List<Integer> zeroInDegreeVertices = new ArrayList<Integer>();
        HashMap<Integer, Integer> degreeMap = new HashMap<Integer, Integer>();

        for (int key : this.graphMapping.keySet())
        {
            int value = this.graphMapping.get(key);

            if (!degreeMap.containsKey(key))
            {
                degreeMap.put(key, 0);
            }

            if (degreeMap.containsKey(value))
            {
                int count = degreeMap.get(value);
                degreeMap.put(value, ++count);
            }
            else
            {
                degreeMap.put(value, 1);
            }
        }

        for (int key : degreeMap.keySet())
        {
            if (degreeMap.get(key) == 0)
            {
                zeroInDegreeVertices.add(key);
            }
        }

        return zeroInDegreeVertices;
    }

    private void InitializeUnvisitedNodes(HashMap<Integer, Integer> graphMapping)
    {
        this.unvisitedVertices = new HashSet<Integer>();

        for (int key : graphMapping.keySet())
        {
            this.unvisitedVertices.add(key);
        }
    }

    private void MarkVerticesAsVisited(
            int startVertex,
            int cycleOffset,
            int cycleLength)
    {
        int currentVertex = startVertex;

        for (int i = 0; i < cycleOffset + cycleLength; ++i)
        {
            this.unvisitedVertices.remove(currentVertex);
            currentVertex = this.graphMapping.get(currentVertex);
        }
    }

    private void MarkVerticesInBranchAsVisited(
            int startVertex,
            int tortoiseSteps)
    {
        int currentVertex = startVertex;
        for (int i = 0; i < tortoiseSteps; ++i)
        {
            this.unvisitedVertices.remove(currentVertex);
            currentVertex = this.graphMapping.get(currentVertex);
        }
    }

    private void RunTortoiseHareAlgorithm(int startVertex)
    {
        int tortoiseVertex = this.graphMapping.get(startVertex);
        int hareVertex = this.graphMapping.get(this.graphMapping.get(startVertex));
        int tortoiseSteps = 1;

        while (true)
        {
            if (!this.unvisitedVertices.contains(tortoiseVertex))
            {
                int cycleNumber = this.vertexToCycleNumberMap.get(tortoiseVertex);
                int weight = this.cycleWeightMap.get(cycleNumber);
                this.cycleWeightMap.put(cycleNumber, weight + tortoiseSteps);
                AddBranchVerticesEntriesToVertexToCycleMapping(startVertex, tortoiseSteps, cycleNumber);
                MarkVerticesInBranchAsVisited(startVertex, tortoiseSteps);
                break;
            }

            if (tortoiseVertex == hareVertex)
            {
                int cycleOffset = ComputeCycleOffset(startVertex, hareVertex);
                int cycleLength = ComputeCycleLength(startVertex, cycleOffset);
                int cycleNumber = GetNextCycleNumber();

                AddEntriesToVertexToCycleMapping(startVertex, cycleOffset, cycleLength, cycleNumber);
                MarkVerticesAsVisited(startVertex, cycleOffset, cycleLength);

                this.cycleLengthMap.put(cycleNumber, cycleLength);
                this.cycleWeightMap.put(cycleNumber, cycleLength + cycleOffset);
                break;
            }

            tortoiseVertex = this.graphMapping.get(tortoiseVertex);
            hareVertex = this.graphMapping.get(this.graphMapping.get(hareVertex));
            ++tortoiseSteps;
        }
    }

}
